require 'logger'
require 'generator/generator'
require 'parser/scope'
require 'parser/variable'
require 'parser/function'

class Parser
  
  def initialize(scanner)
    @log = Logger.new(STDOUT)
    @log.progname = "Parser"
    @log.datetime_format = ""
    @log.level = Logger::WARN
    
    @scanner = scanner
    @expected_type = :Integer
    @token = scanner.next_token
    Scope.push
  end
  
  def next_token
    @token = @scanner.next_token
  end
  
  # <program> ::=
  #   <program_header> <program_body>
  def program
    @log.debug "Entering <program>"
    name = program_header()
    Generator.start_program(name)
    
    # Encapsulate the run-time functions
    scope = Scope.current
    int_var = Variable.new(scope, "Integer", :Integer)
    char_var = Variable.new(scope, "Character", :Character)
    str_var = Variable.new(scope, "String", :String)
    # Character get()
    fn = Function.new(scope, "get", char_var, [])
    Scope.insert_runtime(fn)
    # Integer get()
    fn = Function.new(scope, "get", int_var, [])
    Scope.insert_runtime(fn)
    # String get()
    fn = Function.new(scope, "get", str_var, [])
    Scope.insert_runtime(fn)
    # Integer put(Character)
    fn = Function.new(scope, "put", int_var, [char_var])
    Scope.insert_runtime(fn)
    # Integer put(Integer)
    fn = Function.new(scope, "put", int_var, [int_var])
    Scope.insert_runtime(fn)
    # Integer put(String)
    fn = Function.new(scope, "put", int_var, [str_var])
    Scope.insert_runtime(fn)
    # Integer sqrt(Integer)
    fn = Function.new(scope, "sqrt", int_var, [int_var])
    Scope.insert_runtime(fn)
    # Character int2char(Integer)
    fn = Function.new(scope, "int2char", char_var, [int_var])
    Scope.insert_runtime(fn)
    # Integer char2int(Character)
    fn = Function.new(scope, "char2int", int_var, [char_var])
    Scope.insert_runtime(fn)
    
    Scope.push
    program_body()
    Scope.pop
    Generator.end_program(name)
    
    return name
  end
  
  # <program_header> ::=
  #   program <identifier> is
  def program_header
    @log.debug "Entering <program_header>"
    match(:Keyword_program)
    name = match(:Identifier).literal
    match(:Keyword_is)
    return name
  end
  
  # <program_body> ::=
  #   (<declaration> ;)*
  #   begin
  #   (<statement> ;)*
  #   end program
  def program_body
    @log.debug "Entering <program_body>"
    decs = Array.new
    while @token.token_type != :Keyword_begin
      decs << declaration()
      match(:Operator_semicolon)
    end

    Generator.program_body()

    match(:Keyword_begin)
    stmts = Array.new
    while @token.token_type != :Keyword_end
      stmts << statement()
      match(:Operator_semicolon)
    end

    match(:Keyword_end)
    match(:Keyword_program)
    return [decs, stmts]
  end
  
  # <declaration> ::=
  #   <function_declaration>
  # | <variable_declaration
  def declaration
    @log.debug "Entering <declaration>"
    case(@token.token_type)
    when :Keyword_function
      func_dec = function_declaration()
      return func_dec
    when :Keyword_integer, :Keyword_character, :Keyword_string
      var_dec = variable_declaration()
      (type, name, is_array, size) = var_dec
      offset = Scope.current.next_offset(size)
      var = Variable.new(Scope.current, name, type, "Reg[FP]", offset, is_array, size)
      Scope.current.insert_variable(var)
      var.allocate
      return var
    else
      raise "Unable to parse a declaration."
    end
  end
  
  # <function_declaration> ::=
  #   <function_header>
  #   <function_body>
  def function_declaration
    @log.debug "Entering <function_declaration>"
    # Parse out the function signature
    header = function_header()
    (return_type, fn_name, params_desc) = header
    
    parent_scope = Scope.current
    # Push a new scope for the function's local variables
    Scope.push
    
    current_scope = Scope.current
    parameters = Array.new
    params_desc.each do |param|
      (type, name, is_array, size) = param
      offset = current_scope.next_offset(size)
      var = Variable.new(current_scope, name, type)
      var.addr_offset = offset
      var.is_array = is_array
      var.size = size
      var.is_reference = true
      current_scope.insert_variable(var)
      parameters << var
    end
    offset = current_scope.next_offset
    ret_var = Variable.new(current_scope, fn_name, return_type)
    ret_var.addr_offset = offset
    current_scope.insert_variable(ret_var)
    
    @log.info "Function Declaration: name=#{fn_name}"
    fn = Function.new(Scope.current, fn_name, ret_var, parameters)
    parent_scope.insert_function(fn)
    fn.header()
    body = function_body()
    fn.footer()
    
    # Pop the function's local scope
    Scope.pop
    return [fn, body]
  end
  
  # <function_header> ::=
  #   function <identifier> ( <parameter_list> )
  #   returns <type_mark> is
  def function_header
    @log.debug "Entering <function_header>"
    match(:Keyword_function)
    name = match(:Identifier).literal
    match(:Operator_left_paren)
    parameters = parameter_list()
    match(:Operator_right_paren)

    match(:Keyword_returns)
    return_type = type_mark()
    match(:Keyword_is)
    return [return_type, name, parameters]
  end
  
  # <parameter_list> ::=
  #   <parameter> <parameter_list_follow>
  # | epsilon
  def parameter_list
    @log.debug "Entering <parameter_list>"
    if(@token.literal == ')')
      # epsilon
      return []
    end
    var_dec = parameter()
    parameters = [var_dec]
    param = parameter_list_follow()
    unless param.nil?
      parameters = param.unshift(var_dec)
    end
    return parameters
  end
  
  # <parameter_list_follow> ::=
  #   , <parameter_list>
  # | epsilon
  def parameter_list_follow
    @log.debug "Entering <parameter_list_follow>"
    if @token.token_type == :Operator_comma
      match(:Operator_comma)
      parameters = parameter_list()
      return parameters
    else
      # epsilon
      @log.debug "Taking Epsilon"
      return nil
    end
  end
  
  # <parameter> ::=
  #   <variable_declaration>
  def parameter
    @log.debug "Entering <parameter>"
    var_dec = variable_declaration()
    return var_dec
  end
  
  # <function_body> ::=
  #   (<declaration> ;)*
  #   begin
  #   (<statement> ;)*
  #   end function
  def function_body
    @log.debug "Entering <function_body>"
    decs = Array.new
    while @token.token_type != :Keyword_begin
      decs << declaration()
      match(:Operator_semicolon)
    end
    match(:Keyword_begin)
    stmts = Array.new
    while @token.token_type != :Keyword_end
      stmts << statement()
      match(:Operator_semicolon)
    end
    match(:Keyword_end)
    match(:Keyword_function)
    return [decs, stmts]
  end
  
  # <variable_declaration> ::=
  #   <type_mark> <identifier> [[<array_size>]]
  def variable_declaration
    @log.debug "Entering <variable_declaration>"
    
    # Parse out the type
    type = type_mark()
    
    # Parse out the variable name
    name = match(:Identifier).literal
    
    size = 1
    if (is_array = @token.token_type == :Operator_left_square)
      match(:Operator_left_square)
      size = array_size()
      match(:Operator_right_square)
    end
    @log.info "Variable Declaration: [#{type}, #{name}, #{is_array}, #{size}]"
    return [type, name, is_array, size]
  end
      
  # <type_mark> ::=
  #   integer
  # | character
  # | string
  def type_mark
    @log.debug "Entering <type_mark>"
    type_mark = nil
    case(@token.token_type)
    when :Keyword_integer
      match(:Keyword_integer)
      return :Integer
    when :Keyword_character
      match(:Keyword_character)
      return :Character
    when :Keyword_string
      match(:Keyword_string)
      return :String
    else
      raise "Unable to parse a type mark."
    end
  end

  # <array_size> ::=
  #   <number>
  def array_size
    @log.debug "Entering <array_size>"
    number = match(:Number).literal.to_i
    return number
  end
  
  # <statement> ::=
  #   <assignment_statement>
  # | <if_statement>
  # | <while_statement>
  def statement
    @log.debug "Entering <statement>"
    stmt = nil
    case(@token.token_type)
    when :Identifier
      stmt = assignment_statement()
    when :Keyword_if
      stmt = if_statement()
    when :Keyword_while
      stmt = while_statement()
    else
      raise "Unable to parse a statement."
    end
    return stmt
  end
  
  # <assignment_statement> ::=
  #   <destination> := <expression>
  def assignment_statement
    @log.debug "Entering <assignment_statement>"
    dest = destination()
    (var, is_array, index_reg) = dest
    t1 = var.var_type
    match(:Operator_colon_equal)
    # Give a type-hint for the RHS
    @expected_type = t1
    exp = expression()
    (reg, t2, val) = exp
    # Type-checking
    unless(t1 == t2)
      raise "Operator := requires both operands to be of the same type. (found #{t1} := #{t2})"
    end
    var.store(reg, is_array, index_reg)
    return var
  end
  
  # <destination> ::=
  #   <identifier> [[<expression>]]
  def destination
    @log.debug "Entering <destination>"
    name = match(:Identifier).literal
    var = Scope.current.get_variable(name)
    if(@token.token_type == :Operator_left_square)
      # It's an indexed array
      match(:Operator_left_square)
      # Give a type-hint for the index
      @expected_type = :Integer
      exp = expression()
      match(:Operator_right_square)
      (exp_reg, exp_type, exp_val) = exp
      # Type-checking
      unless(exp_type == :Integer)
        raise "Array index must be of type Integer. (found #{exp_type})"
      end
      return [var, true, exp_reg]
    else
      # It's just a regular variable name
      return [var, false, 0]
    end
  end
      
  # <if_statement> ::=
  #   if <expression> then (<statement>;)+
  #   [else (<statement>;)+]
  #   end if
  def if_statement
    @log.debug "Entering <if_statement>"
    match(:Keyword_if)
    if_id = Scope.next_if
    Generator.raw_line("IF_#{if_id}:")
    # Give a type-hint for the conditional
    @expected_type = :Integer
    exp = expression()
    (reg, type, val) = exp
    # Type-checking
    unless(type == :Integer)
      raise "IF requires a conditional expression of type Integer. (found #{type})"
    end
    Generator.write_line("if(Reg[#{reg}] == 0) goto IF_ELSE_#{if_id};", "")
    match(:Keyword_then)
    token_type = @token.token_type
    stmts = Array.new
    begin
      stmts << statement()
      match(:Operator_semicolon)
      token_type = @token.token_type
    end until(token_type == :Keyword_else or token_type == :Keyword_end)
    Generator.write_line("goto IF_END_#{if_id};", "")
    Generator.raw_line("IF_ELSE_#{if_id}:")
    else_stmts = Array.new
    if(token_type == :Keyword_else)
      match(:Keyword_else)
      begin
        else_stmts << statement()
        match(:Operator_semicolon)
      end until(@token.token_type == :Keyword_end)
    end
    Generator.raw_line("IF_END_#{if_id}:")
    match(:Keyword_end)
    match(:Keyword_if)
    return [exp, stmts, else_stmts]
  end
  
  # <while_statement> ::=
  #   while <expression> (<statement>;)*
  #   end while
  def while_statement
    @log.debug "Entering <while_statement>"
    match(:Keyword_while)
    while_id = Scope.next_while
    Generator.raw_line("WHILE_#{while_id}:")
    # Give a type-hint for the conditional
    @expected_type = :Integer
    exp = expression()
    (reg, type, val) = exp
    # Type-checking
    unless(type == :Integer)
      raise "WHILE requires a conditional expression of type Integer. (found #{type})"
    end
    Generator.write_line("if(Reg[#{reg}] == 0) goto WHILE_END_#{while_id};", "")
    stmts = Array.new
    until(@token.token_type == :Keyword_end)
      stmts << statement()
      match(:Operator_semicolon)
    end
    Generator.write_line("goto WHILE_#{while_id};", "")
    Generator.raw_line("WHILE_END_#{while_id}:")
    match(:Keyword_end)
    match(:Keyword_while)
    return [exp, stmts]
  end
  
  # <expression> ::=
  #   <relation> <expression_follow>
  def expression
    @log.debug "Entering <expression>"
    rel1 = relation()
    (op, rel2) = expression_follow()
    if(op.nil?)
      return rel1
    else
      (r1, t1, v1) = rel1
      (r2, t2, v2) = rel2
      # Type-checking
      unless(t1 == :Integer and t2 == :Integer)
        raise "Operator #{op} requires both operands to be of type Integer. (found #{t1} #{op} #{t2})"
      end
      reg = Generator.operation(r1, op, r2)
      return [reg, :Integer, [:Operation, r1, op, r2]]
    end
  end
  
  # <expression_follow> ::=
  #   + <relation>
  # | - <relation>
  # | & <relation>
  # | | <relation>
  # | epsilon
  def expression_follow
    @log.debug "Entering <expression_follow>"
    case(@token.literal)
    when '+'
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_plus)
      rel = relation()
      return ['+', rel]
    when '-'
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_minus)
      rel = relation()
      return ['-', rel]
    when '&'
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_amp)
      rel = relation()
      return ['&', rel]
    when '|'
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_pipe)
      rel = relation()
      return ['|', rel]
    else
      # epsilon
      @log.debug "Taking Epsilon"
      return [nil, nil]
    end
  end
  
  # <relation> ::=
  #   <term> <relation_follow>
  def relation
    @log.debug "Entering <relation>"
    term = term()
    (op, rel) = relation_follow()
    if (op.nil?)
      return term
    else
      (r1, t1, v1) = term
      (r2, t2, v2) = rel
      # Type-checking
      unless(t1 == t2)
        raise "Operator #{op} requires both operands to be of the same type. (found #{t1} #{op} #{t2})"
      end
      reg = Generator.operation(r1, op, r2)
      return [reg, :Integer, [:Operation, r1, op, r2]]
    end
  end
  
  # <relation_follow> ::=
  #   < <relation>
  # | <= <relation>
  # | > <relation>
  # | >= <relation>
  # | == <relation>
  # | != <relation>
  # | epsilon
  def relation_follow
    @log.debug "Entering <relation_follow>"
    case(@token.literal)
    when '<'
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_less)
      rel = relation()
      return ['<', rel]
    when '<='
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_less_equal)
      rel = relation()
      return ['<=', rel]
    when '>'
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_greater)
      rel = relation()
      return ['>', rel]
    when '>='
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_greater_equal)
      rel = relation()
      return ['>=', rel]
    when '=='
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_equal_equal)
      rel = relation()
      return ['==', rel]
    when '!='
      # Give a type-hint for the second relation
      @expected_type = :Integer
      match(:Operator_not_equal)
      rel = relation()
      return ['!=', rel]
    else
      # epsilon
      @log.debug "Taking Epsilon"
      return [nil, nil]
    end
  end
  
  # <term> ::=
  #   <factor> <term_follow>
  def term
    @log.debug "Entering <term>"
    fac = factor()
    (op, term) = term_follow()
    if (op.nil?)
      return fac
    else
      (r1, t1, v1) = fac
      (r2, t2, v2) = term
      # Type-checking
      unless(t1 == :Integer and t2 == :Integer)
        raise "Operator #{op} requires both operands to be of type Integer. (found #{t1} #{op} #{t2})"
      end
      reg = Generator.operation(r1, op, r2)
      return [reg, :Integer, [:Operation, r1, op, r2]]
    end      
  end
  
  # <term_follow> ::=
  #   * <term>
  # | / <term>
  # | epsilon
  def term_follow
    @log.debug "Entering <term_follow>"
    case(@token.literal)
    when '*'
      # Give a type-hint for the second term
      @expected_type = :Integer
      match(:Operator_star)
      t = term()
      return ['*', t]
    when '/'
      # Give a type-hint for the second term
      @expected_type = :Integer
      match(:Operator_slash)
      t = term()
      return ['/', t]
    else
      # epsilon
      @log.debug "Taking Epsilon"
      return [nil, nil]
    end
  end
  
  # <factor> ::=
  #   ( <expression> )
  # | <number>
  # | <string>
  # | <name_or_fcn_call>
  def factor
    @log.debug "Entering <factor>"
    if @token.literal == '('
      match(:Operator_left_paren)
      exp = expression()
      match(:Operator_right_paren)
      return exp
    else
      case(@token.token_type)
      when :Number
        num = match(:Number).literal
        reg = Scope.next_register
        Generator.literal(:Integer, "#{num}", reg)
        return [reg, :Integer, [:Literal_Integer, num]]
      when :String
        str = match(:String).literal
        reg = Scope.next_register
        size = str.length
        if(size == 1)
          # Character
          offset = Scope.current.next_offset(size)
          var = Variable.new(Scope.current, "*CHR LIT*", :Character, "Reg[FP]", offset, false, size)
          var.allocate()
          Generator.literal(:String, "'#{str[0].chr}'", [reg, var])
          return [reg, :Character, [:Literal_String, str]]
        else
          # String
          size = size + 1 # add 1 for the \0 at the end
          offset = Scope.current.next_offset(size)
          var = Variable.new(Scope.current, "*STR LIT*", :String, "Reg[FP]", offset, false, size)
          var.allocate()
          Generator.literal(:String, "#{str.inspect}", [reg, var])
          return [reg, :String, [:Literal_String, str]]
        end
      else
        return name_or_fcn_call()
      end
    end
  end

  # <name_or_fcn_call> ::=
  #   <identifier> <name_or_fcn_call_follow>
  def name_or_fcn_call
    @log.debug "Entering <name_or_fcn_call>"
    name = match(:Identifier).literal
    (kind, follow) = name_or_fcn_call_follow()
    if(kind == :Epsilon)
      # Identifier
      reg = Scope.next_register
      var = Scope.current.get_variable(name)
      type = var.var_type
      var.load(reg)
      return [reg, type, [:Identifier, var]]
    elsif(kind == :Array_Index)
      # Array Index
      index_reg = follow[0]
      reg = Scope.next_register
      var = Scope.current.get_variable(name)
      type = var.var_type
      var.load(reg, true, index_reg)
      return [reg, type, [:Array_Index, var, index_reg]]
    elsif(kind == :Argument_List)
      # Function Call
      arguments = follow
      # arguments is an Array of Variables and index registers
      fn = Scope.current.get_function(name, @expected_type, arguments)
      type = fn.return_var.var_type
      arguments.each_index do |i|
        # Pass the arguments to the function
        fn.pass_argument(i, arguments[i])
      end
      fn.call()
      reg = :RV
      return [reg, type, [:Function, fn, arguments]]
    else
      @log.error "name_or_function_call fell through all cases:\nkind=#{kind}\nfollow=#{follow.inspect}"
      return [:ERROR, "name_or_function_call fell through all cases"]
    end
  end
  
  # <name_or_fcn_call_follow> ::=
  #   ( <argument_list> )
  # | [ <expression> ]
  # | epsilon
  def name_or_fcn_call_follow
    @log.debug "Entering <name_or_fcn_call_follow>"
    case(@token.literal)
    when '(':
      match(:Operator_left_paren)
      arguments = argument_list()
      match(:Operator_right_paren)
      return [:Argument_List, arguments]
    when '['
      match(:Operator_left_square)
      index = expression()
      match(:Operator_right_square)
      return [:Array_Index, index]
    else
      # epsilon
      @log.debug "Taking Epsilon"
      return [:Epsilon, nil]
    end
  end
  
  # <argument_list> ::=
  #   <expression> <argument_list_follow>
  # | epsilon
  def argument_list
    @log.debug "Entering <argument_list>"
    if(@token.literal == ')')
      # epsilon
      @log.debug "Taking Epsilon"
      return []
    end
    exp = expression()
    (reg, type, val) = exp
    # Arguments are passed by reference
    # Create temp Variables where needed
    # Pass-through addresses of existing variables
    if(val[0] == :Array_Index)
      (tag, var, index_reg) = val
    elsif(val[0] == :Identifier)
      (tag, var) = val
      index_reg = nil
    else
      index_reg = nil
      is_array = false
      size = 1
      offset = Scope.current.next_offset(size)
      var = Variable.new(Scope.current, "*TEMP*", type, "Reg[FP]", offset, is_array, size)
      var.allocate
      var.store(reg)
    end
    
    arglist_f = argument_list_follow()
    output = [[var, index_reg]]
    unless(arglist_f.nil?)
      output = output.concat(arglist_f)
    end
    return output
  end

  # <argument_list_follow ::=
  #   , <argument_list>
  # | epsilon
  def argument_list_follow
    @log.debug "Entering <argument_list_follow>"
    if @token.literal == ','
      match(:Operator_comma)
      arglist = argument_list()
      return arglist
    else
      # epsilon
      @log.debug "Taking Epsilon"
      return nil
    end
  end
  
  # Returns a Token if a match was found, throws an Exception otherwise
  # Consumes one token if match is found
  def match(token_type)
    @log.debug "Matching #{@token} to token type #{token_type}"
    if @token.token_type == token_type
      output = @token
      next_token
      return output
    else
      raise "Unable to match token #{@token} with: #{token_type}"
    end
  end
end